#define _CRT_SECURE_NO_WARNINGS 1

ListNode* partition(ListNode* pHead, int x) {
    struct ListNode* ghead, * lhead, * gtail, * ltail;
    struct ListNode* cur, * nex;
    ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
    lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
    cur = pHead;
    nex = cur->next;
    while (cur)
    {
        if (cur->val < x)
        {
            ltail->next = cur;
            ltail = ltail->next;
        }
        else
        {
            gtail->next = cur;
            gtail = gtail->next;
        }
        cur = nex;
        if (nex != NULL)
            nex = nex->next;

    }
    gtail->next = NULL;
    ltail->next = NULL;

    ltail->next = ghead->next;

    struct ListNode* re = lhead->next;

    free(ghead);
    free(lhead);

    return re;


}